package company.other;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class C1 {

    public static void main(String[] args) {
        getList(new int[]{10, 1, 2, 7, 6, 1, 5}, 8);
        System.out.println(ans);
    }

    static List<List<Integer>> ans = new ArrayList<>();

    public static List<List<Integer>> getList(int[] nums, int target) {
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        for (int i = 0; i < nums.length; i++) {
            helper(nums, i, 0, new ArrayList<>(), target);
        }
        return ans;
    }

    private static void helper(int[] nums, int startIndex, int count, List<Integer> list, int target) {
        if (count == target) {
            ans.add(list);
            return;
        }
        if (startIndex >= nums.length || count + nums[startIndex] > target)
            return;
        // 选
        ArrayList<Integer> tmp = new ArrayList<>(list);
        tmp.add(nums[startIndex]);
        helper(nums, startIndex + 1, count + nums[startIndex], tmp, target);
        // 不选
        ArrayList<Integer> tmp1 = new ArrayList<>(list);
        helper(nums, startIndex + 1, count, tmp1, target);
    }
}
